#include "BTreeNode.h"

using namespace std;

void BTLeafNode::ToString()
{
  cout << "B+ Tree Leaf Node:" << endl;
  cout << "pageid: " << (int)getNextNodePtr() << endl;
  cout << "Key Count: " << getKeyCount() << endl;
  cout << "RecordId [pid, sid], key" << endl;

  int numElements = 0;
  
  for(; numElements<numKeys; numElements++)
  {
    RecordId* record = (RecordId *)(buffer+(numElements*elementSize));
    int* keyPtr = (int *)(buffer+(numElements*elementSize)+sizeof(RecordId));
    cout << "[" << ((int)record->pid) << ", " << record->sid << "], " << (*keyPtr) << endl;
  }
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
  int errCode = pf.read(pid, buffer);
  if(errCode != 0)
  {
    return errCode;
  }

  int numElements = 0;
  
  for(; numElements<maxElements; numElements++)
  {
    RecordId* record = (RecordId *)(buffer+(numElements*elementSize));
    if(!(record->pid >= 0))
    {
      break;
    }
  }

  numKeys = numElements;

  return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{

  if(numKeys < maxElements)
  {
    RecordId* record = (RecordId *)(buffer+(numKeys*elementSize));
    record->pid = -1;
  }

  return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
  return numKeys;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
  if(numKeys >= maxElements)
  {
    return -1;
  }

  int curElement = 0;
  int carryKey;
  RecordId carryRID;
  carryRID.pid = -2;

  for(; curElement < maxElements; curElement++)
  {
    RecordId* record = (RecordId *)(buffer+(curElement*elementSize));
    int* keyPtr = (int *)(buffer+(curElement*elementSize)+sizeof(RecordId));

    if(carryRID.pid == -2 && ( curElement == numKeys || key < *keyPtr ))
    {
      carryKey = *keyPtr;
      carryRID.pid = record->pid;
      carryRID.sid = record->sid;

      *keyPtr = key;
      record->pid = rid.pid;
      record->sid = rid.sid;

      numKeys++;
    }
    else if(carryRID.pid != -2)
    {
      int tempKey = *keyPtr;
      RecordId tempRID;
      tempRID.pid = record->pid;
      tempRID.sid = record->sid;

      *keyPtr = carryKey;
      record->pid = carryRID.pid;
      record->sid = carryRID.sid;

      carryKey = tempKey;
      carryRID.pid = tempRID.pid;
      carryRID.sid = tempRID.sid;
    }
  }

  return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
  int curElement = numKeys/2;

  for(; curElement < maxElements; curElement++)
  {
    RecordId* record = (RecordId *)(buffer+(curElement*elementSize));
    int* keyPtr = (int *)(buffer+(curElement*elementSize)+sizeof(RecordId));
    sibling.insert(*keyPtr, *record);
  }

  numKeys -= (numKeys - numKeys/2);

  int firstKey;
  RecordId firstRID;
  sibling.readEntry(0, firstKey, firstRID);

  if(key >= firstKey)
  {
    sibling.insert(key, rid);
  }
  else
  {
    insert(key, rid);
  }
  
  return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
  int curElement = 0;
  
  for(; curElement<maxElements; curElement++)
  {
    int* keyPtr = (int *)(buffer+(curElement*elementSize)+sizeof(RecordId));
    
    if(curElement>=numKeys || *keyPtr >= searchKey)
    {
      //TODO: SHOULD THE FIRST CASE, WE REACH AN EMPTY NODE BE AN ERROR OR THE ELEMENT WE RETURN?
      eid = curElement;
      return 0;
    }
  }

  return -1;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
  RecordId* record = (RecordId *)(buffer+(eid*elementSize));
  int* keyPtr = (int *)(buffer+(eid*elementSize)+sizeof(RecordId));

  key = *keyPtr;
  rid.pid = record->pid;
  rid.sid = record->sid;

  return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
  PageId* pageIdPtr = (PageId *)(buffer+PageFile::PAGE_SIZE-sizeof(PageId));
  return *pageIdPtr;
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
  PageId* pageIdPtr = (PageId *)(buffer+PageFile::PAGE_SIZE-sizeof(PageId));
  *pageIdPtr = pid;
  return 0;
}

void BTNonLeafNode::ToString()
{
  cout << "B+ Tree Non Leaf Node:" << endl;
  cout << "Key Count: " << getKeyCount() << endl;
  cout << "pageid, key" << endl;

  int numElements = 0;
  
  for(; numElements<numKeys; numElements++)
  {
    PageId* pidPtr = (PageId *)(buffer+(numElements*elementSize));
    int* keyPtr = (int *)(buffer+(numElements*elementSize)+sizeof(PageId));
    cout << ((int)*pidPtr) << ", " << (*keyPtr) << endl;
  }
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
  int errCode = pf.read(pid, buffer);
  if(errCode != 0)
  {
    return errCode;
  }

  int numElements = 0;
  
  for(; numElements<maxElements; numElements++)
  {
    PageId* pid = (PageId *)(buffer+(numElements*elementSize));
    if(!(pid >= 0))
    {
      break;
    }
  }

  numKeys = numElements;

  return 0;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
  if(numKeys < maxElements)
  {
    PageId* pidPtr = (PageId *)(buffer+(numKeys*elementSize));
    *pidPtr = -1;
  }

  return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
  return numKeys;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
  if(numKeys >= maxElements)
  {
    return -1;
  }

  int curElement = 0;
  PageId carryPID = -2;
  int carryKey;

  for(; curElement < maxElements; curElement++)
  {
    PageId* pidPtr = (PageId *)(buffer+(curElement*elementSize));
    int* keyPtr = (int *)(buffer+(curElement*elementSize)+sizeof(RecordId));

    if(carryPID == -2 && ( curElement == numKeys || key < *keyPtr ))
    {
      carryKey = *keyPtr;
      carryPID = *pidPtr;

      *keyPtr = key;
      *pidPtr = pid;

      numKeys++;
    }
    else if(carryPID != -2)
    {
      int tempKey = *keyPtr;
      PageId tempPID = *pidPtr;

      *keyPtr = carryKey;
      *pidPtr = carryPID;

      carryKey = tempKey;
      carryPID = tempPID;
    }
  }

  return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
  int curElement = numKeys/2;
  int* midKeyPtr = (int *)(buffer+(curElement*elementSize)+sizeof(PageId));
  midKey = *midKeyPtr;

  for(; curElement < maxElements; curElement++)
  {
    PageId* pidPtr = (PageId *)(buffer+(curElement*elementSize));
    int* keyPtr = (int *)(buffer+(curElement*elementSize)+sizeof(PageId));
    sibling.insert(*keyPtr, *pidPtr);
  }

  numKeys -= (numKeys - numKeys/2);

  if(key >= midKey)
  {
    sibling.insert(key, pid);
  }
  else
  {
    insert(key, pid);
  }
  
  return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
  int curElement = 0;
  
  for(; curElement<maxElements; curElement++)
  {
    PageId* pidPtr = (PageId *)(buffer+(curElement*elementSize));
    int* keyPtr = (int *)(buffer+(curElement*elementSize)+sizeof(PageId));
    
    if(curElement >= numKeys || *keyPtr > searchKey)
    {
      pid = *pidPtr;
      return 0;
    }
  }

  return -1;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
  numKeys = 0;
  insert(key, pid1);
  
  PageId* pidPtr = (PageId *)(buffer+elementSize);
  *pidPtr = pid2;

  return 0;
}
